import java.util.HashMap;
import java.util.HashSet;

public class MinWindow {

    public static void main(String[] args) {
        MinWindow minWindow = new MinWindow();
        System.out.println(minWindow.minWindow("ADOBECODEBANC", "ABC"));
    }

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        int count = t.length();
        for (int i = 0; i < count; i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int l = 0;
        int r = 0;
        String ans = "";
        while (r < s.length()) {
            char c = s.charAt(r);
            if (map.containsKey(c)) {
                if (map.get(c) > 0) --count;
                map.put(c, map.get(c) - 1);
            }
            while (count == 0) {
                char c1 = s.charAt(l);
                if (map.containsKey(c1)) {
                    if (map.get(c1) >= 0) break;
                    map.put(c1, map.get(c1) + 1);
                }
                ++l;
            }
            if (count == 0 && (ans.length() == 0 || s.substring(l, r + 1).length() < ans.length())) ans = s.substring(l, r + 1);
            ++r;
        }
        return ans;
    }

    public String minWindow1(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        HashMap<Character, Integer> curMap = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        char[] tChars = t.toCharArray();
        char[] sChars = s.toCharArray();
        for (int i = 0; i < tChars.length; i++) {
            char c = tChars[i];
            map.put(c, map.getOrDefault(c, 0) + 1);
            set.add(c);
        }
        int l = 0;
        int r = 0;
        int ansL = l;
        int ansR = Integer.MAX_VALUE;
        while (r < sChars.length) {
            while (!set.isEmpty() && r < sChars.length) {
                char c = sChars[r];
                if (map.containsKey(c)) {
                    curMap.put(c, curMap.getOrDefault(c, 0) + 1);
                    if (curMap.get(c).compareTo(map.get(c)) >= 0) set.remove(c);
                }
                ++r;
            }
            while (set.isEmpty()) {
                if (r - l <= ansR - ansL) {
                    ansL = l;
                    ansR = r;
                }
                if (map.containsKey(sChars[l])) {
                    curMap.put(sChars[l], curMap.get(sChars[l]) - 1);
                    if (curMap.get(sChars[l]).compareTo(map.get(sChars[l])) < 0) set.add(sChars[l]);
                }
                ++l;
            }
        }
        if (ansR == Integer.MAX_VALUE) return "";
        return s.substring(ansL, ansR);
    }
}
